#include <iostream>
#include <vector>
#include <string>
using namespace std;

//几乎所有题目都是不用考虑奇偶的，一般都是向下取整就满足条件
//但是有时间还是要多想一想

/**
 * 数组A 元素个数大于等于2，元素值为正整数
 * 将A分成两个数组，要求两个数组的元素个数尽可能的接近，且求和的差值最大
 * 其中个数接近是主要，求和差值最大是次要
 *
 * 思想：满足个数接近，那么就是等分
 * 将较小的n/2个元素放到左边，较大的n/2个元素放到右边，就可以保证差值最大
 * 因为不要求子数组内部有序，这里使用快排的思想，但是要做一些更改
 * 将数组的prov元素找到合适的位置之后，判断prov元素的位置，如果是在左半边
 * 那么下次寻找要找prov的左半边
 *
 * 时间复杂度O(n^2)，每轮找prov的位置平均n/2次，prov位于中间位置的概率为n/2
 * 空间复杂度O(1) 只用到了prov这个辅助空间
 *
 *
 * 可以举例子说明 对于奇数个，分法不同，结果是一样的如：1 ， 2 ， 1000
 * [1,2] 和 [1000] 结果为 |3-1000|=997
 * [1] 和[2, 1000] 结果为 |1-1002|=1001
 * 所以左半边要少一点，才能取到最大值，所以向下取整没有问题
 *
 */
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
int split(vector<int> &A, int left, int right);
//优雅的实现，比答案中的好一点
int solution(vector<int> &A)
{
    int index = 0;
    int left = 0;
    int right = A.size() - 1;
    int target_index=A.size()/2-1;
    do
    {
        index = split(A, left,right); // 获取每次的prov的大小
        if (index < target_index)
            left = index + 1;
        else if (index > target_index)
        {           
            right = index - 1;
        }
        else
        {
            break;
        }
    } while (true);
    return index;
}
int split(vector<int> &A, int left, int right)
{
    int prov = A[left];
    while (left < right) // 寻找prov的位置
    {
        while (left < right && A[right] >= prov)
        {
            right--;
        }
        if (left != right)
            A[left] = A[right];
        while (left < right && A[left] <= prov)
        {
            left++;
        }
        if(left!=right)
            A[right]=A[left];
    }
    A[left] = prov;
    return left;
}
// 测试
int main(void)
{
    vector<int> arr = {1000, 1, 2};
    int index=solution(arr);

    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << " ";
    }

    int s1=0;
    int s2=0;
    for(int i=0;i<=index;i++) s1+=arr[i];
    for(int i=index+1;i<arr.size();i++) s2+=arr[i];
    printf("s1 %d  and s1 %d  and |s1-s2| %d \n ",s1,s2,abs(s1-s2));
    return 0;
}